package algorithms.sort;

import java.util.Arrays;

/**
 * 归并排序（递归方式）
 * 时间复杂度O(N*logN)
 * 额外空间复杂度：O(n)
 * 思路：
 *      1.数组从中间分两半，左边与右边分别排序
 *      2.归并一下，左右两边的数组通过下标比较将最小的（相等取左边）放入额外的数组中。
 * 与传统排序来说：
 *   1.优化了比较的效率，传统排序每次比较n次才搞定一个数
 *
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {1,7,5,4,2,324,2,2,3,6,34,5,25,345,23,234,532,234,45,234,525,234,24};
        long start = System.currentTimeMillis();
        process(arr,0,arr.length-1);
        long end = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println(end);
        System.out.println(end);
        System.out.println("耗时："+(end-start)+"ms");

//        int[] arr = {1,3,4,2,5};
//        System.out.println(smallSum(arr));

    }

    /**
     * 递归处理
     * @param arr 数组
     * @param l 左边的下标
     * @param r 右边的下标
     * @return
     */
    public static void process(int[] arr,int l,int r){
        if(l == r) {// 只有一个数的时候停止
//            System.out.println(arr[l]);
            return;
        }

        int mid = l + ((r-l) >> 1);// 防止l+r越界
        process(arr,l,mid);
        process(arr,mid+1,r);
        merge(arr,l,mid,r);
    }

    /**
     *
     * @param arr
     * @param l 左边的下标
     * @param m 中间的下标
     * @param r 右边的下标
     */
    private static void merge(int[] arr, int l, int m, int r) {
        // 额外数组
        int[] help = new int[r-l+1];
        int helpIndex = 0;
        int p1 = l;// 左边数组开始位置
        int p2 = m+1;// 右边数组开始位置
        // 左右数组都在范围内:谁小拷贝谁，相同拷贝左边
        while (p1<=m && p2 <= r){
            help[helpIndex++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 左边数组越界，将右边剩下的数拷贝到help中
        while (p2 <= r){
            help[helpIndex++]=arr[p2++];
        }
        // 右边数组越界，将左边剩下的数拷贝到help中
        while (p1 <= m){
            help[helpIndex++]=arr[p1++];
        }
        // 数组复制到原数组中
        for(int i=0;i<help.length;i++){
            arr[l+i]=help[i];
        }
        System.out.println("help："+Arrays.toString(help));

    }

    /**
     * 小和问题
     * 1，3，4，2，5  = 16
     * @param arr
     */
    private static int smallSum(int[] arr) {
        return smallSumProcess(arr, 0, arr.length - 1);
    }

    private static int smallSumProcess(int[] arr,int l,int r) {
        if(l == r)
            return 0;
        // 中点
        int mid = l + ((r-l) >> 1);
        return smallSumProcess(arr,l,mid)// 左边
                +
                smallSumProcess(arr,mid + 1,r)// 右边
                +
                smallSumMerge(arr,l,mid,r);// 合并
    }

    private static int smallSumMerge(int[] arr,int l,int m,int r) {
        int[] helps = new int[r-l+1];
        int index = 0;// helps下标
        int p1 = l;// 左指针
        int p2 = m + 1;// 右指针
        int result = 0;// 结果
        // 正常比较:p1，p2都没有越界
        while (p1 <= m && p2 <= r) {
            //  小和
            result += arr[p1] < arr[p2] ? arr[p1] * (r-p2 + 1) : 0;
            helps[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 左边越界(不产生小和)
        while (p2 <= r) {
            helps[index++] = arr[p2++];
        }
        // 右边边越界(不产生小和)
        while (p1 <= m) {
            helps[index++] = arr[p1++];
        }
        // 数组复制到原数组中
        for(int i=0;i<helps.length;i++){
            arr[l+i]=helps[i];
        }
        return result;
    }







}
